package array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created by fengliejv on 2017/10/16.
 */
public class MajorityElementII229 {

    //摩尔投票法
    public List<Integer> majorityElement(int[] nums) {
        int num1 = Integer.MIN_VALUE;
        int count1 = 0;
        int num2 = Integer.MIN_VALUE;
        int count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (num1 == nums[i] && count1 > 0) {
                count1++;
            } else if (num2 == nums[i] && count2 > 0) {
                count2++;
            }else if (count1 == 0) {
                num1 = nums[i];
                count1++;
            } else if (count2 == 0) {
                num2 = nums[i];
                count2++;
            }else {
                count1--;
                count2--;
            }
        }
        int c1 = 0;
        int c2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == num1){
                c1++;
            }
            if(nums[i] == num2){
                c2++;
            }
        }
        List<Integer> result  =  new ArrayList<>();
        if(c1>nums.length/3){
            result.add(num1);
        }
        if(num1!=num2&&c2>nums.length/3){
            result.add(num2);
        }

        return result;
    }

//哈希计数法
//    public List<Integer> majorityElement(int[] nums) {
//        HashMap<Integer,Integer> map = new HashMap<>();
//        List<Integer> list = new ArrayList<>();
//        if(nums.length==0){
//            return list;
//        }
//        int count = nums.length/3;
//        for (int i = 0; i < nums.length; i++) {
//            int cal;
//            if(map.containsKey(nums[i])){
//                cal = map.get(nums[i]);
//                cal++;
//
//            }else {
//                 cal =1;
//
//            }
//            if(cal>count){
//                cal=Integer.MIN_VALUE;
//                list.add(nums[i]);
//            }
//            map.put(nums[i],cal);
//        }
//        return list;
//    }
}
